//
//  串的定义和实现.hpp
//  408数据结构
//
//  Created by Cai Yuanhao on 2022/3/27.
//

#ifndef ________hpp
#define ________hpp
#endif /* ________hpp */
#include <stdio.h>
#include <string.h>


#define MAXLEN 255
#include <stdlib.h>


//定长顺序存储表示
typedef struct{
    char ch[MAXLEN];
    int length;
} SString;

//堆分配存储表示
typedef struct{
    char *ch;
    int length;
} HString;

//块链存储表示
#define CHUNKSIZE 4 /* 可由用户定义的块大小 */
typedef struct Chunk
{
  char ch[CHUNKSIZE];
  struct Chunk *next;
}Chunk;
typedef struct
{
  Chunk *head,*tail; /* 串的头和尾指针 */
  int curlen; /* 串的当前长度 */
}LString;

bool StrAssign(SString &T,const char *chars){
    if (strlen(chars)>MAXLEN) {
        return false;
    }
    int i=1;
    while (chars[i-1]!='\0') {
        T.ch[i]=chars[i-1];
        i++;
    }
    T.length=i-1;
    return true;
}

bool StrCopy(SString &T,SString S){
//    把S复制给T
    for (int i=1; i<=S.length; i++) {
        T.ch[i]=S.ch[i];
        T.length++;
    }
    
    return true;
}

bool isEmpty(SString S){
    if (S.length==0) {
        return true;
    }
    return false;
}

//int min(int a,int b){
//    if (a>b) {
//        return b;
//    }
//    if (a<b) {
//        return a;
//    }
//    return a;
//}
//
//int StrCompare(SString S,SString T){
////    比较俩字符串大小，如果S<T则返回-1，S=T返回0,S>T返回1
//    int i =0;
//    while ((i<S.length)&&(i<T.length)) {
//        if (S.ch[i]<T.ch[i]) {
//            return -1;
//        }
//        else if (S.ch[i]>T.ch[i])
//        {    return 1;}
//        else{
//            i++;
//            continue;
//        }
//    }
//    if (i==T.length&&i!=S.length) {
//        return 1;
//    }
//    else if (i==S.length&i!=T.length){
//        return -1;
//    }
//    else{
//        return 0;
//    }
//}

// 比较俩字符串大小，如果S<T则返回-1，S=T返回0,S>T返回1,优化后
int StrCompare(SString S,SString T){
    for (int i =1; i<=S.length&&i<=T.length; i++) {
        if (S.ch[i]!=T.ch[i]) {
            return S.ch[i]-T.ch[i];
        }
    }
    return S.length-T.length;
}


int StrLength(SString S){
    return S.length;
}

bool SubString(SString &Sub,SString S,int pos,int len){
    Sub.length=0;
//    在串中找位置是pos，长度是len的子串
    if ((pos+len-1)>S.length) {
        return false;
    }
    for (int i=pos; i<pos+len; i++) {
        Sub.ch[i-pos+1]=S.ch[i];
        Sub.length++;
    }
    return true;
}

void getNext(SString T,int next[]){
    int i=1;
//    next[0]=0;
    next[1]=0;
    int j=0;
    while (i<T.length) {
        if (j==0||T.ch[i]==T.ch[j]) {
            ++i;
            ++j;
            next[i]=j;
        }
        else{
            j=next[j];}
    }
}

int IndexKMP(SString S,SString T){
//    T是模式串
//    for (int i=1; i<=T.length; i++) {
//        printf("%d",next[i]);
//    }
    int next[T.length+1];
    getNext(T, next);
    int i=1,j=1;
    while (i<=S.length&&j<=T.length) {
        if (j==0||S.ch[i]==T.ch[j]) {
            ++i;++j;
        }
        else{
            j=next[j];
        }
    }
    if (j>T.length) {
        return i-T.length;
    }
    return 0;
}

void StrPrint(SString S){
    for (int i=1; i<=S.length; i++) {
        printf("%c",S.ch[i]);
    }
}

int *GetNextval(SString S){
    int next[S.length+1];
    getNext(S, next);
    int *nextval=(int*)malloc(sizeof(int)*(S.length+1));
    nextval[1]=0;
    for (int j=2; j<=S.length; j++) {
        if (S.ch[next[j]]==S.ch[j]) {
            nextval[j]=nextval[next[j]];
        }
        else
            nextval[j]=next[j];
    }
//    for (int i=1; i<S.length+1; i++) {
//        printf("%d ",nextval[i]);
//    }
    return nextval;
}


int IndexKMP_nextval(SString S,SString T){
//    T是模式串
//    for (int i=1; i<=T.length; i++) {
//        printf("%d",next[i]);
//    }
    int *next=GetNextval(T);
    int i=1,j=1;
    while (i<=S.length&&j<=T.length) {
        if (j==0||S.ch[i]==T.ch[j]) {
            ++i;++j;
        }
        else{
            j=next[j];
        }
    }
    if (j>T.length) {
        return i-T.length;
    }
    return 0;
}






